#ifndef LEETCODE_CN_CPP_PROBLEMS_239_H
#define LEETCODE_CN_CPP_PROBLEMS_239_H

#include <deque>
#include <vector>

using namespace std;

namespace problem_239
{

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        deque<pair<int, int>> dq; //(nums[i], i)，保持队列头部为最大值
        for (int i = 0; i < k - 1; ++i)
        {
            while (!dq.empty() && dq.back().first < nums[i])
                dq.pop_back();
            if (dq.empty() || dq.back().first >= nums[i])
                dq.emplace_back(nums[i], i);
        }
        vector<int> result;
        for (int i = k - 1; i < nums.size(); ++i)
        {
            while (!dq.empty() && dq.back().first < nums[i])
                dq.pop_back();
            if (dq.empty() || dq.back().first >= nums[i])
                dq.emplace_back(nums[i], i);
            while (dq.front().second <= i - k)
                dq.pop_front();
            result.push_back(dq.front().first);
        }
        return move(result);
    }
};

} // namespace problem_239

#endif //LEETCODE_CN_CPP_PROBLEMS_239_H
